class Solution {
public:
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        if (!matrix||rows<1&&cols<1&&!str)
            return false;
        bool* visited=new bool[rows*cols];
        memset(visited,0,rows*cols);
        int pathlength=0;
        for(int i=0;i<rows;++i)
            {
            for(int j=0;j<cols;++j)
                {
                if(haspathcore(matrix,rows,cols,i,j,str,pathlength,visited))
                    return true;
            }
        }
        delete[] visited;
        return false;
    }
 
    bool haspathcore(char* matrix,int rows,int cols,int i,int j,char* str,int& pathlength,bool* visited)
        {
        if(str[pathlength]=='\0')
            return true;
        bool haspath =false;
        if(i>=0&&i<rows&&j>=0&&j<cols&&matrix[i*cols+j]==str[pathlength]&&!visited[i*cols+j])
            {
            pathlength++;
             visited[i*cols+j]=true;
            haspath=haspathcore(matrix,rows,cols,i-1,j,str,pathlength,visited)||haspathcore(matrix,rows,cols,i+1,j,str,pathlength,visited)||
                haspathcore(matrix,rows,cols,i,j-1,str,pathlength,visited)||haspathcore(matrix,rows,cols,i,j+1,str,pathlength,visited);
         
        if(!haspath)
            {
            pathlength--;
            visited[i*cols+j]=false;
        }
    }
         return haspath;  
    }
};